package arithmetic;

import java.awt.datatransfer.MimeTypeParseException;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: Jie
 * @Date: 2019/1/14 18:12
 * @Function :
 *
 * https://leetcode-cn.com/submissions/detail/11633623/
 *
 *225 使用【队列】实现【栈】的下列操作：
 * push(x) -- 元素 x 入栈
 * pop() -- 移除栈顶元素
 * top() -- 获取栈顶元素
 * empty() -- 返回栈是否为空
 *
 * linkedList size 1是关键
 *
 */
public class A_04_QueueToStack {
    public static void main(String[] args) {
//        MyStack myStack = new MyStack();
        MyStackLeetCode myStack = new MyStackLeetCode();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
//        System.out.println(myStack.top());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.empty());
    }
}
//92ms
class MyStack {

    private  LinkedList<Integer> master= new LinkedList<>();
    private  LinkedList<Integer> help = new LinkedList<>();

    /** Initialize your data structure here. */
    public MyStack() {
    }

    /** Push element x onto stack. */
    public void push(int x) {
        master.add(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        while (master.size()>1){
            help.push(master.poll());
        }
        int poll = master.poll();
        LinkedList<Integer> temp = master;
        master = help;
        help = temp;
        if (temp==null)
            return -1;
        return poll;
    }

    /** Get the top element. */
    public int top() {
        if (master.size()>1){
            while (master.size()>1){
               help.push(master.poll());
            }
        }else if (master.size()==1){
            return master.peek();
        }else if (help.size()>0){// master <= 0
            while (help.size()>0){
                master.push(help.poll());
            }
            while (master.size()>1){
                help.push(master.poll());
            }
        }
        if (master.isEmpty()){
            return -1;
        }
        return master.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {

        return master.isEmpty()&&help.isEmpty();
    }
}

//没有copy 互相 更改引用
class MyStackLeetCode {

    /** Initialize your data structure here. */
    Queue<Integer> lQueue = new LinkedList<>();
    Queue<Integer> rQueue = new LinkedList<>();
    public MyStackLeetCode() {

    }

    /** Push element x onto stack. */
    public void push(int x) {
        lQueue.add(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        while(lQueue.size() > 1) {
            rQueue.add(lQueue.poll());
        }
        int tmp = lQueue.poll();
        Queue<Integer> temp = lQueue;
        lQueue = rQueue;
        rQueue = temp;

        return tmp;

    }

    /** Get the top element. */
    public int top() {
        while (lQueue.size() > 1) {
            rQueue.add(lQueue.poll());
        }
        return lQueue.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return lQueue.isEmpty() && rQueue.isEmpty();
    }
}

